НУЛП, ІКНІ, САПР
Тема
оцінка
підпис
Ізоморфізм графів
№ залікової:
Дискретні моделі в САПР
Викладач:
Мета роботи : метою лабораторної роботи є вивчення і дослідження основних підходів до встановлення ізоморфізму графів.
Короткі теоретичні відомості :
Теорія графів дає простий, доступний і потужній інструмент побудови моделей і рішення задач впорядкування взаємозвязаних обєктів. Нині є багато проблем де необхідно дослідити деякі складні системи з допомогою впорядкування їх елементів. До таких проблем відносяться і задачі ідентифікації в електричних схемах, в авіації, в органічній хімії і т.д. Вирішення таких
проблем досягається з допомогою встановлення ізоморфізму графів. Два графа G=(X,U,P) і G'=(X',U',P') називаються ізоморфними, якщо між їх вершинами, а також між їхніми ребрами можна встановити взаємно однозначне співвідношення X <-> X', U <-> U', що зберігає інцидентність, тобто таке, що для всякої пари (x,y)єX ребра u є U, що з'єднує їх, обов'язково існує пара (x',y') є X' і ребро u' є U', що з'єднує їх, і навпаки. Тут P - предикат, інцидентор графа G. Зауважимо, що відношення ізоморфізму графіврефлексивне, симетричне і транзитивне, тобто представляє собою еквівалентність.
На даний час існує досить детальна класифікація розроблених методів рішення такого типу задач /1/. Розглядаючи комбінаторно-логічну природу вказаної задачі можна всі роботи в цьому напрямку розділити на дві групи: рішення теоретичної задачі встановлення ізоморфізму простих графів; розробка наближених методів, які найбільш повно враховують
обмеження і специфіку задачі з застосуванням характерних ознак об’єкту дослідження.
До першої групи відносяться алгоритми: повного перебору і почергового “підвішування” графів за вершини.
а) Одним з найпростіших з точки зору програмної реалізації, є алгоритм перевірки ізоморфізму графів повним перебором(можливої перенумерації вершин), але складність цього алгоритму є факторіальною.
б) Почергове “підвішування” графів за вершини (всі ребра
зрівноважені).
Суть цього алгоритму полягає в знаходженні однакових “підвішаних” графів (за довільні вершини), ізоморфність яких визначаємо. При чому в одному з графів почергово змінюється вершина за яку він “підвішується”. Ізоморфізм графів визначається по їх матрицях суміжності, які формуються по однотипних правилах: індекс в матриці вершини за яку закріплений (“підвішаний”) граф рівний одиниці; кортеж вершин в матриці визначається рівнями сусідів; кортеж вершин в межах кожного рівня сусідів визначається степінню вершини, а також кількістю ребер над нею і нижче її.
Реалізація алгоритму (Java) :
public void getSum() { arrayListOne = new ArrayList<Integer>(); for(int i=0;i<nodes;i++) { int sum=0; for(int j=0;j<nodes;j++) { sum+=adjecencyMatrixOne[i][j]; } arrayListOne.add(sum); } arrayListTwo = new ArrayList<Integer>(); for(int i=0;i<nodes;i++) { int sum=0; for(int j=0;j<nodes;j++) { sum+=adjecencyMatrixTwo[i][j]; } arrayListTwo.add(sum); } } public boolean checkIsomorphism() { for(int i=0;i<nodes;i++) { if(arrayListOne.get(i)!=arrayListTwo.get(i)) { return false; } } return true; }
Інструкція по експлуатації:
Для роботи програми необхідно запустити файл Lab_5_DM.java . Спочатку необхідно ввести кількість вершин графа, далі матрицю суміжності. В результаті роботи програма визначає чи є графи ізоморфні та виводить результати на екран.
Граф:
Рис.1. Граф G. Рис.2. Граф H.
Результат виконання:
***HELP***
0. Програма перевіряє графи на ізоморфізм!
Для коректної роботи програми необхідно:
1. Ввести кількість вершин графу.
2. Ввести матриці суміжності(цілі числа) для двох графів.
3. Нумерація вершин графа починається з 1 з інкрементом в 1 (1,2,3...) ...
